//Given an integer array nums, you need to find one continuous subarray that if 
//you only sort this subarray in ascending order, then the whole array will be 
//sorted in ascending order. 
//
// Return the shortest such subarray and output its length. 
//
// 
// Example 1: 
//
// 
//Input: nums = [2,6,4,8,10,9,15]
//Output: 5
//Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the 
//whole array sorted in ascending order.
// 
//
// Example 2: 
//
// 
//Input: nums = [1,2,3,4]
//Output: 0
// 
//
// Example 3: 
//
// 
//Input: nums = [1]
//Output: 0
// 
//
// 
// Constraints: 
//
// 
// 1 <= nums.length <= 10⁴ 
// -10⁵ <= nums[i] <= 10⁵ 
// 
//
// 
//Follow up: Can you solve it in O(n) time complexity? Related Topics Array Two 
//Pointers Stack Greedy Sorting Monotonic Stack 👍 4517 👎 192


package leetcode.editor.en;

public class _581_ShortestUnsortedContinuousSubarray {
    public static void main(String[] args) {
        Solution solution = new _581_ShortestUnsortedContinuousSubarray().new Solution();
        solution.findUnsortedSubarray(new int[]{2,6,4,8,10,9,15});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int begin = 0, end = -1, min = nums[nums.length-1], max = nums[0];

            for (int i = 1; i < nums.length; i++) {
                if (nums[i]<max){
                    end = i;
                }else {
                    max = nums[i];
                }
                if (nums[nums.length-i-1]>min){
                    begin = nums.length-i-1;
                }else {
                    min = nums[nums.length-i-1];
                }
            }
            return end-begin+1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}